Somme de radicaux
L'introduction de cet article est soit absente, soit non conforme aux conventions de Wikipédia ().
Ces motifs sont peut-être précisés sur la page de discussion. — Découvrez comment faire pour en améliorer la rédaction.
En théorie de la complexité, il existe un problème ouvert de savoir si certaines informations concernant une somme de radicaux peuvent être calculées en temps polynomial en fonction de la taille d'entrée, c'est-à-dire du nombre de bits nécessaires pour représenter cette somme. Ce problème algorithmique est important en géométrie algorithmique, puisque le calcul de la distance euclidienne entre deux points dans le cas général implique le calcul d'une racine carrée. Ainsi le périmètre d'un polygone, ou la longueur d'une chaîne polygonale prend la forme d'une somme de radicaux[1].
La somme des radicaux est définie comme une combinaison linéaire finie de radicaux:
![{\displaystyle \sum _{i=1}^{n}k_{i}{\sqrt[{r_{i}}]{x_{i}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88f8e5154b52c32759c00bcfd8940b97ad925b4f)
où sont des entiers naturels et sont des nombres réels.
La plupart des recherches théoriques sur la géométrie algorithmique du caractère combinatoire prennent le modèle de calcul de la RAM réelle de précision infinie, c'est-à-dire un ordinateur abstrait dans lequel des nombres et des opérations réels sont effectués avec une précision infinie, et la taille d'entrée d'un nombre réel et le coût d'une opération sont constantes[2],[3].
En particulier, l'intérêt pour la géométrie est le problème de déterminer le signe de la somme des radicaux. Par exemple, la longueur d'un chemin polygonal dans lequel tous les sommets ont des coordonnées entières peut être exprimée en utilisant le théorème de Pythagore comme une somme de racines carrées entières, afin de déterminer si un chemin est plus long ou plus court; Cette expression est une somme de radicaux.
En 1991, Blömer a proposé un algorithme de Monte-Carlo de temps polynomial pour déterminer si une somme de radicaux est nulle, ou plus généralement si elle représente un nombre rationnel[4]. Le résultat de Blömer ne résout pas la complexité informatique de trouver le signe de la somme des radicaux, cela implique que si ce problème est de classe NP, il est aussi en co-NP[4].
Articles connexes
[modifier | modifier le code]Références
[modifier | modifier le code]- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sum of radicals » (voir la liste des auteurs).
- (en) Wolfgang Mulzer et Günter Rote, « Minimum-Weight Triangulation Is NP-Hard », Journal of the ACMM (en), proceedings of the 22nd Annual Symposium on Computational Geometry (en), Sedona, 5-7 juin 2006, vol. 55, no 2, .
- (en) Franco P. Preparata et Michael Ian Shamos, Computational Geometry : An Introduction, New York, Springer, coll. « Texts and monographs in computer science », , 6e éd. (1re éd. 1985) (ISBN 978-3-540-96131-4 et 3-540-96131-3).
- (en) Johannes Grabmeier, Erich Kaltofen et Volker Weispfenning, Computer Algebra Handbook : Foundations, Applications, Systems ; [with CD-ROM], New York, Springer, , 637 p. (ISBN 978-3-540-65466-7, lire en ligne).
- Johannes Blömer, « Computing sums of radicals in polynomial time », dans Proceedings 32nd Annual Symposium on Foundations of Computer Science, (DOI 10.1109/SFCS.1991.185434), p. 670
